package cn.aylog.recursion;

/**
 * 练习:
 *  迷宫回溯
 */
public class Demo1 {
    public static void main(String[] args) {
        Maze maze = new Maze(8,7);
        maze.setWall(2, 2);
        maze.setWall(3, 1);
        maze.setWall(3, 2);
        maze.setWall(5, 3);
        maze.setWall(5, 4);
        maze.setWall(5, 5);
        System.out.println("原始迷宫地图:");
        maze.showMaze();
        maze.play(1, 1);
        System.out.println("迷宫路线~");
        maze.showMaze();
    }
}

class Maze {
    private int maze[][];
    private static final int BLOCK = 0; // 可通行
    private static final int WALL = 1; // 墙壁
    private static final int ROAD = 2; // 通路
    private static final int DEAD = 3; // 死胡同

    public Maze(int row, int col) {
        maze = new int[row][col];
        init();
    }

    /**
     * 迷宫初始化,四周增加墙壁
     */
    private void init() {
        int row = maze.length;
        int col = maze[0].length;
        for(int y=0; y<row; y++) {
            setWall(y, 0);
            setWall(y, col -1);
        }
        for(int x=0; x<col; x++) {
            setWall(0, x);
            setWall(row-1, x);
        }
    }

    /**
     * 设置指定的点为墙
     */
    public void setWall(int x, int y) {
        maze[x][y] = WALL;
    }

    public void setFlag(int x, int y, int flag) {
        maze[x][y] = flag;
    }

    /**
     * 输出地图
     */
    public void showMaze() {
        int row = maze.length;
        int col = maze[0].length;
        for(int x=0; x<row; x++) {
            for(int y=0; y<col; y++) {
                System.out.print(maze[x][y] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 往指定方向走
     */
    private boolean playUp(int x, int y) {
        return play(x-1, y);
    }
    private boolean playDown(int x, int y) {
        return play(x+1, y);
    }
    private boolean playLeft(int x, int y) {
        return play(x, y-1);
    }
    private boolean playRight(int x, int y) {
        return play(x, y+1);
    }

    /**
     * 开始走迷宫
     * 策略: 下->右->上->左
     */
    public boolean play(int x, int y) {
        int row = maze.length;
        int col = maze[0].length;
        System.out.println("步骤:");
        showMaze();
        // 结束标志
        if(maze[row-2][col-2] == ROAD) {
            return true;
        } else if(maze[x][y] == BLOCK) {
            // 假设当前点能到达
            setFlag(x, y, ROAD);
            if(playDown(x, y)) { //
                return true;
            } else if(playRight(x, y)) { //
                return true;
            } else if(playUp(x, y)) { //
                return true;
            } else if(playLeft(x, y)) { //
                return true;
            } else {
                // 四周都走不同, 死胡同
                setFlag(x, y, DEAD);
                return false;
            }
        } else {
            return false;
        }
    }
}
